class MERGE{

	static int[] num = {5, 8, 3, 9, 7, 2, 7, 4, 0};

	public static void main(String[] args) {

		int test_num[];
		test_num = new MERGE().sort(num, 0, num.length-1);
		
		for(int i : test_num) {
			System.out.print(i+",");
		}
		
	}

	public int[] sort(int[] a, int start, int end) {

		int mid = (start + end)/2;

		if (start < end) {
			//左边
			sort(a, start, mid);
			//右边
			sort(a, mid+1, end);
			//左右归并
			merge(a,start,mid, end);

		}
		
		return a;
	}
	
	public static void merge(int[] a, int low, int mid, int high) {

        int[] temp = new int[high-low+1];
        int i= low;		//左指针
        int j = mid + 1;	//右指针	
        int k=0;
        
        //把较小的数先移动到临时数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        
        //把左边剩余的数移入数组
        while(i<=mid){
            temp[k++] = a[i++];
        }
        
        //把右边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        
        //将临时数组中的数据复制到源数组中
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }

    }
}